1.1. Need for Secrecy of Computer Information
This invention relates generally to improving secrecy in a computer system to prevent unwanted access to information. It relates more particularly to a method of reducing the potential for covert-channel communications in the computer system (and thus reducing the frequency at which operations such as cache-clearing must be performed to impede such communications), and of directly closing a scheduler timing channel.
(Those of ordinary skill will recognize that secrecy, i.e., the prevention of unauthorized access to information, is but one component of computer "security," as that term is commonly used. Other components include "integrity," namely the prevention of tampering with the information, and the prevention of unauthorized denial of service. The Department of Defense publication entitled Department of Defense Trusted Computer System Evaluation Criteria, sometimes referred to as the "Orange Book," describes a number of common system security objectives and evaluation criteria for secure computer systems.)
Historically, information has been a highly sought-after asset of businesses and governments. Prior to the computer revolution, locked filing cabinets, safes, secured buildings, guards, alarm systems and video surveillance were used to protect important information. Proper physical security measures, such as these, were usually adequate to prevent the undesirable dissemination of information.
Because computers are now being used to store information, instead of filing cabinets, these physical security measures have become less effective. Not only can all users access information within a given computer system, but physical security cannot necessarily protect against communications between the computer system and remote devices. Therefore, many computerized information systems include internal security which may provide users with different levels of access to the computerized information, and may protect the computerized information from other types of undesirable access.
1.2. Secrecy Classifications and Access Rules
A computer system designed for promoting security typically may follow a set of nondiscretionary rules and another set of discretionary rules for access determination.
(a) Secrecy Levels. In order to follow the nondiscretionary rules, each "subject" (i.e., a person or process attempting to access information) and each "object" (i.e., the information that is the object of the access attempt) may be given a security identifier, which is frequently referred to as a "secrecy level." In other words, the data may be classified into various secrecy levels that are reflective of the sensitivity of the data. For example, top secret information might have the highest secrecy level, and only users authorized to have access to the highest secrecy level would thus be permitted to access top-secret information.
(b) Secrecy Categories. Information within a given secrecy level may also be "categorized" for further restriction of access. As a hypothetical example, assume that, within a secrecy level designated "Top Secret," there exist three categories of information, Grape, Orange, and Strawberry. Access to each category may be restricted to those having not only the requisite top-secret clearance but clearance for the particular category as well (e.g., on a need-to-know basis).
(c) Secrecy Classes. The term "secrecy class" is customarily defined as comprising (i) a secrecy level and (ii) zero or more secrecy categories. In the example of the previous paragraph, three secrecy classes are mentioned, namely Top Secret-Grape, Top Secret-Orange, and Top Secret-Strawberry. "Top Secret" with no secrecy categories would also be an example of a secrecy class, as would "Secret Grape-Orange-Strawberry."
In mediating access to memory or other storage, a computer system may compare the secrecy class of a subject to the secrecy class of an object, and determine if the subject is allowed to access the object. In this manner, access to sensitive information can be limited to a select user group.
1.3. Nondiscretionary Rules
Two fundamental nondiscretionary rules help restrict access by users to information. These rules are the "simple security condition," which aims to prevent a subject from reading more highly classified objects; and the "*-property [pronounced `star property`]" rule, the goal of which is to prevent a subject from writing less highly classified objects. Both are aimed at blunting attacks that might be deliberate (e.g., malicious or simply reckless) or accidental, and from a human user or from software.
(a) Simple Security Condition. The "simple security condition" can help prevent a user or a computer process from accessing (e.g., reading) data unless (a) his or its authorized secrecy level is greater or equal to the secrecy level of the information, and (b) his or its secrecy class includes all categories of the data in question. For example, consider a subject whose secrecy class was SECRET-NATO (i.e., the subject's secrecy level is SECRET, and the subject's only secrecy category is NATO). This subject would not be allowed to access data of any secrecy category (e.g., NATO, NUCLEAR, or no-category) whose secrecy level was TOP SECRET. Nor would the subject be allowed to read data of any secrecy level, even CONFIDENTIAL data, that had a secrecy category not possessed by the subject (e.g., CONFIDENTIAL-NUCLEAR).
(b) Star Property. The "*-property" rule (also called the "confinement property"), endeavors to prevent illicit indirect viewing of a first type or class of object through copying to a second type of object that has a "lower" secrecy class than the first object. The *-property addresses this by preventing a subject from writing to a second type of object (e.g., by copying information to the second object from the first object) unless (a) the secrecy level of the second type of object is greater than or equal to the secrecy level of the subject, and (b) the above-mentioned secrecy category clearances of the subject and objects are such that the writing operation is authorized.
For example, an unclassified file might be unmodifiable by a TOP SECRET process to prevent TOP SECRET information from being copied to the unclassified file. Therefore, the computer system should endeavor to prevent access by undesirable users, even if they are aided and abetted by Trojan horse software as discussed in the next section.
1.4. The "Trojan Horse" Problem and Covert-Channel Communication
Not only should a computer system protect the computerized information from undesirable users, but also from undesirable software that operates illicitly in a "high" secrecy class. "Trojan horse" software appears to be legitimate soft-ware, but in fact is designed to operate illicitly within the computer system. A Trojan horse may be implanted in commonly used software, and may access a user's files without the knowledge of the user.
For example, a Trojan horse might operate as part of a TOP SECRET process. The Trojan horse might be able to access a file and copy the information contained therein into another file. This alone is not necessarily a problem, but it could be a serious problem if the information were to be passed on to a user or process not authorized to receive it. The problem can be made worse by the fact that a Trojan horse program is typically difficult to find, even after it has been functioning.
Under the *-property of a computer system, a program operating on behalf of a user (or a Trojan-horse process) should be prevented from passing information to any other user having a "lower" secrecy class. Trojan horse programs therefore attempt to use covert channels to transmit information illicitly. A "covert channel" in a computer system is a communication channel that allows one or more processes operating in a computer system (e.g., one or more programs) to transfer information in a manner that violates the system's security policy, e.g., to transfer information to unauthorized users.
(a) Scheduler Covert Timing Channels. An example of a covert channel is found in the illicit use of the timing of scheduler functions. As those of ordinary skill are aware, scheduler functions (or functions performing the same role) are part of the operating system of a multiprocessing computer system. These functions serve to allocate CPU time as a resource among various processes.
Suppose that two processes are running on a computer system: (1) a "Trojan-horse" sending process in the TOP SECRET-GRAPE access class, for illicitly sending information, and (2) a "spy" receiving process in the UNCLASSIFIED secrecy class for receiving the illicitly sent information. Further suppose that the computer system's scheduling functions permit each of the two processes to operate in "time quanta" of, say, up to 10 milliseconds (ms) at a time before being preempted for other work. Finally, suppose that the receiving process can monitor the time actually used by the sending process, e.g., by noting the real or clock time at which its own quantum begins. (This could happen if the Trojan horse sending process and the spy process are the only two running processes, which in turn could occur during periods of very low computer-system activity, e.g., late at night.)
The sending process can then signal the receiving process by modulating the portion that it actually uses of the time quanta allocated to it. For example, the sending process might generate an "on" bit by performing timeconsuming operations (e.g., by busy-looping or using NOPs to waste CPU cycles) to use up an entire 10-ms quantum. The sending process could similarly generate an "off" bit by stopping at 5 ms (e.g., by using a WAIT instruction to surrender control of the CPU after issuing enough NOPs or other timeconsuming instructions to use up 5 ms). The receiving process, by monitoring the clock time at which it is given control of the CPU (and thus the time actually used by the sending process), can receive and decode messages sent in this manner by the sending process.
(b) Cache-Type Covert Timing Channels. As another example, covert channels can be exploited by modulating the usage of cache storage. As those of ordinary skill are aware, cache storage is a comparatively high speed memory (or disk storage, but memory caches are more effectively used as covert channels and therefore are of greater concern) that is used for temporary storage of frequently-accessed data. Caches are typically used when a memory access operation (e.g., a read operation) is performed that requests information from particular memory locations. The cache controller "receives" the information request and checks whether the request can be satisfied from the comparatively high-speed cache storage. If this is not the case, the cache controller copies not only the requested information from the designated memory locations, but information from memory locations near the designated locations. This increases the likelihood that a subsequent information request can be filled from cache storage. To the extent that requests for data can be satisfied from the cache storage instead of from the comparatively slower regular storage, the speed of the system is thereby increased.
Cache memory is of comparatively small size; thus any given location in cache memory may be mapped to multiple addresses and hence be frequently used by more than one process. Suppose that process A performs a memory access; the cache controller copies the accessed information into certain addresses of the cache memory for future reference. Control of the CPU might subsequently be turned over to another process B which performs its own memory-access operations. Depending on the memory addresses so accessed, the cache memory might be overwritten (thus destroying the information stored in the cache for use by process A). Such an event is known in the art as a "collision."
Information can thus be illicitly transmitted by modulating the time required to complete a read operation. Suppose that a "spy" receiving process is designed routinely to read repeatedly from the same range of addresses in main memory. Every time the spy's read operation can be satisfied by consulting the cache storage instead of main memory, the operation will be completed more quickly. Further suppose that a Trojan-horse sending process can perform memory-access operations that cause "re-use" of the specific cache storage locations that are accessed by the receiving process.
The sending process could then signal the receiving process by selectively performing memory-access operations that cause overwriting of selected portions of the cache storage. The resulting selective collisions in cache storage would force the receiving process to take more time completing a read operation; the receiving process could monitor the time required to complete its reads and decode the resulting information. For example, an "on" bit could be sent by the sending process by causing a collision in cache storage, while an "off" bit could be sent by leaving the cache storage intact.
(c) Closure of Covert Channels. Cache-type covert channels and scheduler covert channels are but two examples of covert channels. A requirement for a computer system to receive an A1, B3, and B2 rating from the National Computer Security Center (NCSC) is to close all or some covert channels, or alternatively to reduce the bandwidth (that is, reduce the rate at which information can be transferred) of such covert channels.
The closure of many covert channels exacts a high performance penalty. One means of closing a cache-type covert channel, for example, is to clear (erase) the cache storage upon some or all "context switches," i.e., when control of the CPU is transferred from one process to another. On modern computers, such an operation will significantly degrade performance.
As for a scheduler-type covert channel, a comparatively straightforward solution to closing the channel is to assign each running process a fixed quantum of CPU time and to idle away any remainder of the assigned time if the running process does not use it up. Because the start of a process's quantum is now unaffected by how much CPU time was consumed by the previous process, this approach effectively closes the channel. This solution is, however, likely to perform poorly because it wastes leftover CPU time.